Graph property

In graph theory, a graph property or graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph.

Contents

Definitions

While graph drawing and graph representation are valid topics in graph theory, in order to focus only on the abstract structure of graphs, a graph property is defined to be a property preserved under all possible isomorphisms of a graph. In other words, it is a property of the graph itself, not of a specific drawing or representation of the graph.

Informally, the term "graph invariant" is used for properties expressed quantitatively, while "property" usually refers to descriptive characterizations of graphs. For example, the statement "graph does not have vertices of degree 1" is a "property" while "the number of vertices of degree 1 in a graph" is an "invariant".

More formally, a graph property is a class of graphs, i.e. a function from graphs to {T,F}, and a graph invariant is a function from graphs to some other set,[1] such as to the natural numbers (for scalar invariants),[2] or to (possibly ordered) sequences of natural numbers (for properties like the degree sequence), or to a polynomial ring,[3] such that isomorphic graphs have the same value.

A graph property is often called hereditary if it also holds for (is "inherited" by) its induced subgraphs.[4] A property is called additive if it is closed under disjoint union.[5] The property of being planar is both hereditary and additive, for example, since a subgraph of a planar graph must be planar, and a disjoint union of two planar graphs must also be planar. The property of being connected is neither, since a subgraph of a connected graph need not be connected, and a disjoint union of two connected graphs cannot be connected.

A graph property is sometimes called monotone increasing (or respectively monotone decreasing) if it is kept under the addition (respectively, the deletion) of edges. For example, the property of being connected is clearly monotone increasing, whereas the property of being 3-colorable is monotone decreasing.

Graph invariants and graph isomorphism

Easily computable graph invariants are instrumental for fast recognition of graph isomorphism, or rather non-isomorphism, since for any invariant at all, two graphs with different values cannot (by definition) be isomorphic. Two graphs with the same invariants may or may not be isomorphic, however.

A graph invariant I(G) is called complete if the identity of the invariants I(G) and I(H) implies the isomorphism of the graphs G and H. Finding such an invariant would imply an easy solution to the challenging graph isomorphism problem. However, even polynomial-valued invariants such as the chromatic polynomial are not usually complete. The claw graph and the path graph on 4 vertices both have the same chromatic polynomial, for example.

Some graph invariants

Scalars

Sequences and polynomials

See also

References

  1. ^ R. Diestel, Graph Theory, 3rd edition, Heidelberg:Springer-Verlag, 2005. [1]
  2. ^ S. Kreutzer, Algorithmic Meta-Theorems, 2008
  3. ^ I. Averbouch, B. Godlin, and J.A. Makowsky, An extension of the bivariate chromatic polynomial, 2008. [2]
  4. ^ Alon, Noga; Shapira, Asaf (2008), "Every monotone graph property is testable", SIAM Journal on Computing 38 (2): 505–522, doi:10.1137/050633445, http://www.math.tau.ac.il/~nogaa/PDFS/monotone1.pdf 
  5. ^ Peter Mihok (1999) "Reducible properties and uniquely partitionable graphs" in: Ronald L. Graham, "Contemporary Trends in Discrete Mathematics", DIMASC Series in Discrete Mathematics and Computer Science, vol. 49, ISBN 0821809636 p. 214